package fibonacci_problem

// 假设开始牧场里有一头奶牛
// 奶牛每年生一头小奶牛
// 小奶牛三年后才可以生奶牛
// 请问第n年，牧场里有多少头奶牛
func GetCrowNums(n int) int {
	// 1 2 3 4 5 6 7
	// 1 2 3 4 6 9 13
	// f(n) = f(n-1) + f(n-3)
	// 今年的奶牛数量等于去年的奶牛数量（已经存在的奶牛的数量） 加 三年前奶牛的数量（新生奶牛数量）
	if n <= 0 {return 0}
	if n <= 4 {return n}
	return GetCrowNums(n-1) + GetCrowNums(n-3)
}

func GetCrowNumsDp(n int) int {
	// 1 2 3 4 5 6 7
	// 1 2 3 4 6 9 13
	// f(n) = f(n-1) + f(n-3)
	// 今年的奶牛数量等于去年的奶牛数量（已经存在的奶牛的数量） 加 三年前奶牛的数量（新生奶牛数量）
	if n <= 0 {return 0}
	if n <= 4 {return n}
	res := 3
	pre := 2
	prepre := 1
	tem1 := 0
	tem2 := 0
	for i:=4; i<=n; i++ {
		tem1 = res
		tem2 = pre
		res = res + prepre
		prepre = tem2
		pre = tem1
	}
	return res
}

func GetCrowNumsMatrix(n int) int {
	// 1 2 3 4 5 6 7
	// 1 2 3 4 6 9 13
	// f(n) = f(n-1) + f(n-3)
	// 今年的奶牛数量等于去年的奶牛数量（已经存在的奶牛的数量） 加 三年前奶牛的数量（新生奶牛数量）
	if n <= 0 {return 0}
	if n <= 4 {return n}

	base := [][]int{
		[]int{1,1,0},
		[]int{0,0,1},
		[]int{1,0,0},
	}
	basePowNR3 := powMatrix(base, n-3)
	return 3*basePowNR3[0][0] + 2*basePowNR3[1][0] + basePowNR3[2][0]
}
